#include <vector>

using std::vector;

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ret;
        vector<int> tmp;
        dfs(ret, tmp, n, k);
        return ret;
    }

    void dfs(vector<vector<int>>& v,vector<int>&tmp,int now,int left) {
        while (now >= left) {
            tmp.push_back(now);
            if (left > 1) {
                dfs(v, tmp, now - 1, left - 1);
            }
            else {
                v.push_back(tmp);
            }
            tmp.pop_back();
            now--;
        }
    }
};